package oj;


public class LC116 {

    //利用上一层已连接好的next指针
    public Node connect(Node root) {
        if(root==null) return null;
        Node pre=root;
        //循环条件是当前节点的left不为空，当只有根节点或叶子节点都串联完后循环退出
        while(pre.left!=null){
            Node tmp=pre;
            while(tmp!=null){
                //将tmp的左右节点都串联起来
                //注意：外层循环已经判断了当前节点的left不为空
                tmp.left.next=tmp.right;
                //下一个不为空说明上一层已经帮我们串联完了，并且 不是每层的最后一个节点，还需要继续串联
                if(tmp.next!=null){
                    tmp.right.next=tmp.next.left;
                }
                //继续往右遍历
                tmp=tmp.next;
            }
            //从下一层的最左边开始遍历
            pre=pre.left;
        }
        return root;
    }

    //层序遍历
//    public Node connect(Node root) {
//        if(root==null) return null;
//        Queue<Node> queue=new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            int size=queue.size();
//            for(int i=0;i<size;i++){
//                Node node=queue.poll();
//                if(i<size-1){
//                    node.next=queue.peek();
//                }
//                if(node.left!=null){
//                    queue.offer(node.left);
//                }
//                if(node.right!=null){
//                    queue.offer(node.right);
//                }
//            }
//        }
//        return root;
//    }
}
